In engineering or/and scientific experiments and applications, one acquires a finite set of samples of the underlying multi-dimensional function of interest. However, because of various physical restrictions of the sampling system, these samples are often obtained on nonuniform grids, thereby preventing the direct use and meaningful interpretation of these data. For example, in medical tomographic imaging such as the two-dimensional (2D) fan-beam computed tomography (CT), single-photon emission computed tomography (SPECT), positron emission tomography (PET), spiral (or helical) CT, diffraction tomography (DT), and magnetic resonance imaging (MRI), the acquired data are often sampled on nonuniform grids in the sinogram space, thus preventing the direct use of existing methods that are computationally efficient and numerically stable for reconstruction of tomographic images. In these situations, one can always use various multi-dimensional interpolation (MDI) methods to convert the samples that lie on nonuniform grids into samples that lie on uniform grids so that they can be processed directly and be presented meaningfully.
A wide variety of MDI methods have previously been developed. However, only the methods that are based upon the Whittaker-Shannon sampling (WST) theorem can potentially provide accurate interpolation results. Unfortunately, these methods generally possesses the shortcoming of a great computational burden, which increases drastically as the number of interpolation dimensions increases ("the curse of the dimensionality"). In attempts to alleviate the computational burden, efforts have been devoted previously to developing efficient interpolation methods. However, these methods are all associated with certain approximations. Virtually all of the MDI methods developed previously calculate the desired uniform samples directly from the measured nonuniform samples, which requires the use of computationally burdensome algorithms if accuracy is to be preserved.
Accordingly, a need exists for a computationally more efficient means for multi-dimensional interpolation. More importantly, none of the previously developed multi-dimensional interpolation methods can be applied to certain multi-dimensional problems such as the one that arises in SPECT.
Accordingly, there is a need to develop a computationally efficient method that can accomplish the multi-dimensional interpolation tasks, for which the existing methods are not applicable.